/*Package leetcode ...
 * @lc app=leetcode.cn id=376 lang=golang
 *
 * [376] 摆动序列
 */
package leetcode

// @lc code=start
func wiggleMaxLength2(nums []int) int {
	n := len(nums)
	if n < 2 {
		return n
	}

	up, down := 1, 1
	for i, v := range nums {
		if i == 0 {
			continue
		}
		if v-nums[i-1] > 0 {
			up = down + 1
		} else if v-nums[i-1] < 0 {
			down = up + 1
		}
	}

	if up >= down {
		return up
	}
	return down
}

func wiggleMaxLength3(nums []int) int {
	n := len(nums)
	if n < 2 {
		return n
	}

	prediff := nums[1] - nums[0]
	ret := 1
	if prediff != 0 {
		ret = 2
	}
	for i, v := range nums {
		if i < 2 {
			continue
		}
		diff := v - nums[i-1]
		if prediff*diff < 0 || (prediff == 0 && diff != 0) {
			prediff = diff
			ret++
		}
	}

	return ret
}

func wiggleMaxLength(nums []int) int {
	var recursion func([]int) (int, int)
	recursion = func(nums []int) (ret int, diff int) {
		n := len(nums)
		if n < 2 {
			return n, 0
		}

		diff = nums[1] - nums[0]
		if diff == 0 {
			return recursion(nums[1:])
		}
		ret, postdiff := recursion(nums[1:])
		if diff*postdiff <= 0 {
			return ret + 1, diff
		}
		return ret, diff
	}

	ret, _ := recursion(nums)
	return ret
}

// @lc code=end
